package com.niuke;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-14 17:43:25
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-14     张李鑫                     1.0         1.0 Version
 */
public class JZ35 {
    public static class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }

    }

    /**
     * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），
     * 请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。
     * 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。
     */
    public static RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        RandomListNode cur = pHead;
        while (cur != null) {
            RandomListNode next = cur.next;
            RandomListNode randomListNode = new RandomListNode(cur.label);
            cur.next = randomListNode;
            randomListNode.next = next;
            cur = next;
        }
        cur = pHead;


        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }

        cur = pHead;
        RandomListNode res = cur.next;
        RandomListNode pre = res;

        while (cur.next.next != null) {
            cur.next=cur.next.next;
            cur = cur.next;
            pre.next = cur.next;
            pre=pre.next;
        }
        cur.next=null;
        return res;
    }

    public static void main(String[] args) {
        RandomListNode randomListNode = new RandomListNode(1);
        RandomListNode randomListNode1 = new RandomListNode(2);
        RandomListNode randomListNode2 = new RandomListNode(3);
        RandomListNode randomListNode3 = new RandomListNode(4);
        RandomListNode randomListNode4 = new RandomListNode(5);
//
        randomListNode.next = randomListNode1;
        randomListNode.random = randomListNode2;

        randomListNode1.next = randomListNode2;
        randomListNode1.random = randomListNode4;

        randomListNode2.next = randomListNode3;
        randomListNode2.random = null;

        randomListNode3.next = randomListNode4;
        randomListNode3.random = randomListNode1;

        RandomListNode clone = Clone(randomListNode);
        System.out.println(clone);
    }
}
